package leetcode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

//Substring with Concatenation of All Words
public class SubstringOfConcatenation {

	public static void main(String[] args) {
//		String s = "barfoothefoobarman";
//		String[] words = {"foo", "bar"};
		String s = "barfoofoothebarfootheman";
		String[] words = {"bar","foo", "the"};
//		String s = "wordgoodgoodgoodbestword";
//		String[] words = {"word","good","best","good"};
		SubstringOfConcatenation object = new SubstringOfConcatenation();
		System.out.println(object.findSubstring(s, words));
	}
	
	public List<Integer> findSubstring(String s, String[] words) {
		List<Integer> res = new ArrayList<>();
		if (s == null || words == null || words.length <= 0) {
			return res;
		}
		//每个单词的长度
		int wordLengh = words[0].length();
		HashMap<String, Integer> map = new HashMap<>(256);
		HashMap<String, Integer> tempMap = new HashMap<>(256);
		for (int i = 0; i < words.length; i++) {
			map.put(words[i], map.getOrDefault(words[i], 0) + 1);
		}
		char[] chas = s.toCharArray();
		int length = chas.length;
		
		Integer times = 0;
		String str = null, tmp = null;
		Integer count = words.length;	//需要匹配的个数
		
		int start = 0;	//用于记录开始的下标
		for (int i = 0; i < wordLengh; i++) {
			start = i;
			count = words.length;
			//感觉是因为这里的原因，新建一个hashMap的时间过长
			tempMap = new HashMap<>(map);
			for(int j = i; j + wordLengh <= length; j += wordLengh){
				str = s.substring(j, j + wordLengh);
				times = tempMap.get(str);
				System.out.println("subString: " + str + "   times: " + times);
				if(times != null){
					tempMap.put(str, times - 1);
					if (times > 0) {
						//这里有一个点要注意的就是如果这儿把map中的数据减一了，那么之后重新再找的时候怎么办
						//所以要用一个新的map
						count--;
					}else{
						while((tempMap.get(str) < 0) && start <= length - wordLengh){
							tmp = s.substring(start, start + wordLengh);
							if(tempMap.containsKey(tmp)){
								tempMap.put(tmp, tempMap.get(tmp) + 1);
							}
							start += wordLengh;
							//same as https://leetcode.com/problems/longest-substring-without-repeating-characters/
							if (tempMap.get(tmp) > 0){
		                    	 count++;
		                    }
							System.out.println("start: " + start + " count:" + count);
						}
					}
					
					if(count == 0){
						res.add(start);
						//将最开始的一个单词次数加1之后继续寻找
						tmp = s.substring(start, start + wordLengh);
						System.out.println("tmp:" + tmp);
						tempMap.put(tmp, tempMap.get(tmp) + 1);
	                    start += wordLengh;
	                    count++;
					}
				}else {
					//如果根本就不含有该字符串
					start = j + wordLengh;
                    count = words.length;
                    tempMap = new HashMap<>(map);
				}
			}
		}
		return res;
	}
	
	//上述代码TLE了
	public List<Integer> findSubstring2(String S, String[] L) {
        List<Integer> res = new LinkedList<>();
        if (L.length == 0 || S.length() < L.length * L[0].length())   return res;
        int N = S.length();
        int M = L.length; // *** length
        int wl = L[0].length();
        Map<String, Integer> map = new HashMap<>(), curMap = new HashMap<>();
        for (String s : L) {
            if (map.containsKey(s))   map.put(s, map.get(s) + 1);
            else                      map.put(s, 1);
        }
        String str = null, tmp = null;
        for (int i = 0; i < wl; i++) {
            int count = 0;  // remark: reset count 
            int start = i;
            for (int r = i; r + wl <= N; r += wl) {
                str = S.substring(r, r + wl);
                if (map.containsKey(str)) {
                    if (curMap.containsKey(str))   curMap.put(str, curMap.get(str) + 1);
                    else                           curMap.put(str, 1);
                    
                    if (curMap.get(str) <= map.get(str))    count++;
                    while (curMap.get(str) > map.get(str)) {
                        tmp = S.substring(start, start + wl);
                        curMap.put(tmp, curMap.get(tmp) - 1);
                        start += wl;
                        
                        //the same as https://leetcode.com/problems/longest-substring-without-repeating-characters/
                        if (curMap.get(tmp) < map.get(tmp)) count--;
                        
                    }
                    if (count == M) {
                        res.add(start);
                        tmp = S.substring(start, start + wl);
                        curMap.put(tmp, curMap.get(tmp) - 1);
                        start += wl;
                        count--;
                    }
                }else {
                    curMap.clear();
                    count = 0;
                    start = r + wl;//not contain, so move the start
                }
            }
            curMap.clear();
        }
        return res;
    }
}
